#define ElemType int

#include "common.h"

typedef struct ListEntry {
	int key;
	int val;
	struct ListEntry* next;
} list_entry;

void push(list_entry* head, int key, int val)
{
	list_entry* tmp = malloc(sizeof(list_entry));
	tmp->key = key;
	tmp->val = val;
	tmp->next = head->next;
	head->next = tmp;
}

void delete (list_entry* head, int key)
{
	for (list_entry* p = head; p->next; p = p->next)
		if (p->next->key == key) {
			list_entry* temp = p->next;
			p->next = temp->next;
			free(temp);
			break;
		}
}

list_entry* find(list_entry* head, int key)
{
	for (list_entry* p = head; p->next; p = p->next)
		if (p->next->key == key)
			return p->next;

	return NULL;
}

void free_list(list_entry* head)
{
	while (head->next) {
		list_entry* next = head->next;
		head->next = next->next;
		free(next);
	}
}

const int BASE = 769;

typedef struct {
	list_entry* data;
} MyHashMap;

MyHashMap* myHashMapCreate()
{
	MyHashMap* ret = malloc(sizeof(MyHashMap));
	ret->data = calloc(BASE, sizeof(list_entry));
	return ret;
}

int hash(int key)
{
	return key % BASE;
}

void myHashMapPut(MyHashMap* obj, int key, int value)
{
	int h = hash(key);
	list_entry* rec = find(obj->data + h, key);
	if (rec)
		rec->val = value;
	else
		push(obj->data + h, key, value);
}

int myHashMapGet(MyHashMap* obj, int key)
{
	int h = hash(key);
	list_entry* rec = find(obj->data + h, key);
	if (rec)
		return rec->val;
	else
		return -1;
}

void myHashMapRemove(MyHashMap* obj, int key)
{
	int h = hash(key);
	delete (obj->data + h, key);
}

void myHashMapFree(MyHashMap* obj)
{
	for (int i = 0; i < BASE; i++)
		free_list(obj->data + i);
	free(obj->data);
}

int main()
{
	return 0;
}

/**
 * Your MyHashMap struct will be instantiated and called as such:
 * MyHashMap* obj = myHashMapCreate();
 * myHashMapPut(obj, key, value);
 
 * int param_2 = myHashMapGet(obj, key);
 
 * myHashMapRemove(obj, key);
 
 * myHashMapFree(obj);
*/
